import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/22 14:49
 * @description 贪心 + 排序
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {2, 2, 4, 5};
        solution.minimalKSum(nums, 4);
    }
    public long minimalKSum(int[] nums, int k) {
        long sum = (long) (1 + k) * k  / 2;
        Arrays.sort(nums);
        // 添加的最大元素
        int last = k;
        // 之前的元素
        int pre = -1;
        for (int num : nums) {
            // 出现重复的元素，跳过
            if (pre == num) {
                continue;
            }
            if (num <= last) {
                last++;
                sum += last - num;
                pre = num;
            }else {
                break;
            }
        }
        return sum;
    }
}
